import java.util.*;

public class Solution126 {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        HashSet<String> word = new HashSet<>(wordList);
        if (!word.contains(endWord)) {
            return res;
        }
        List<String> path = new LinkedList<>();
        path.add(beginWord);
        HashSet<String> vis = new HashSet<>(path);
        Queue<List<String>> queue = new LinkedList<>();
        queue.add(path);
        while (!queue.isEmpty()) {
            HashSet<String> newVis = new HashSet<>();
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                List<String> cur = queue.poll();
                assert cur != null;
                char[] chars = cur.get(cur.size() - 1).toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    char c = chars[i];
                    for (char j = 'a'; j <= 'z'; j++) {
                        if (c == j) {
                            continue;
                        }
                        chars[i] = j;
                        String nextWord = new String(chars);
                        if (word.contains(nextWord) && !vis.contains(nextWord)) {
                            List<String> newPath = new ArrayList<>(cur);
                            newPath.add(nextWord);
                            newVis.add(nextWord);
                            if (nextWord.equals(endWord)) {
                                res.add(newPath);
                            } else {
                                queue.add(newPath);
                            }
                        }
                    }
                    chars[i] = c;
                }
            }
            vis.addAll(newVis);

        }
        return res;
    }
}
